package org.example.leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 406. 根据身高重建队列
 * 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。
 * 每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
 * 请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，
 * 其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
 */
public class Code406 {
    public int[][] reconstructQueue(int[][] people) {
        // 按身高从高到低排序，身高相同时按k值从小到大排序
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1]; // k值小的在前面
            }
            return b[0] - a[0]; // 身高高的在前面
        });

        // 使用链表结构，便于插入操作
        List<int[]> result = new ArrayList<>();

        // 按顺序将每个人插入到对应位置
        for (int[] person : people) {
            result.add(person[1], person); // 在索引为person[1]的位置插入person
        }

        // 转换为数组返回
        return result.toArray(new int[people.length][2]);
    }


}
